1. Field of the Invention
The present invention relates generally to the generation of pseudo-random bit sequences. More particularly, the present invention relates to a system and method for producing functions for generating pseudo-random bit sequences.
2. Background Information
International Telecommunication Union (ITU) recommendations, such as, for example, ITU recommendations O.150, O.151 and O.152, specify various pseudo-random bit sequences (PRBSs) for use in communications test equipment. In general, a PRBS is a binary sequence that exhibits random noise-like properties, but is distinguishable from truly random sequences in that it inherently or deliberately exhibits periodicity. A PRBS generator is a shift register with taps from two or more of its stages mathematically combined in a linear or non-linear fashion, and fed back to the input of the shift register in such a way as to produce a PRBS. In particular, for the ITU recommendations, each sequence is defined in terms of a linear feedback shift register (LFSR) configuration that will produce the required sequence, with, in some cases, additional processing.
Traditionally, PRBSs have been generated by dedicated hardware, such as, for example, a field-programmable gate array (FPGA). Unfortunately, the PRBS algorithms are not, at first blush, readily amenable to efficient software implementation, as their definitions specify algorithms for the generation of one bit at a time, and the generation of each bit requires several single bit operations. Processors are most efficient when processing several bits at a time.
Each PRBS in the ITU recommendations is specified as the output that results from a clocked shift register (SR) with the values of two of the stages being EXCLUSIVE-OR'ed together and fed back into the first stage. The PRBS can then be output from the last stage of the shift register. (In some cases, additional processing is specified, such as, for example, inversion or limits on the number of sequential zero bits.) The parameters defining each PRBS are the number of stages in the shift register, and the stages selected to be fed back to the first stage. For example, certain ITU recommendations specify a PRBS that results from the output of a 31 bit shift register with the values in stages 31 and 28 being EXCLUSIVE-OR'ed and fed back to the first stage. Other sequences are similar, but with different SR lengths and tap points.